package datastructure;

import java.util.ArrayList;
import java.util.List;

public final class SuffixTree {
	private String input;
	private SuffixTreeNode root = new SuffixTreeNode("",null);
	public SuffixTreeNode getRootNode(){
		return root;
	}
	
	public SuffixTree(String input){
		buildTree(input);
	}
	
	public void buildTree(String input){
		this.input = input;
		List<String> suffixList = new ArrayList<String>();
		for(int i = 0;i < input.length();i++){
			suffixList.add(input.substring(i,input.length()));
		}
		for(String suffix:suffixList){
			doGenerateSuffixTree(suffix,root);
		}
	}
	
	private void doGenerateSuffixTree(String input,SuffixTreeNode inputNode){
		boolean hasPut = false;
		for(SuffixTreeNode node:inputNode.getChildNodes()){
			if(input.charAt(0) == node.getValue().charAt(0)){
				hasPut = true;
				for(int i = 0; i < input.length();i++){
					//Node length smaller than suffix length
					if((i == node.getValue().length() - 1) && (i != input.length() - 1)){
						if(!node.getOwners().contains(input)){
							node.addOwner(input);
						}
						doGenerateSuffixTree(input.substring(i + 1),node);
						break;
					}else if(input.charAt(i)!= node.getValue().charAt(i)){
						SuffixTreeNode newNode = new SuffixTreeNode(input.substring(0,i),node.getParent());
						newNode.addOwner(input);
						node.getParent().removeChildNode(node);
						node.getParent().addChildNode(newNode);
						if((i + 1) != input.length()){
							SuffixTreeNode n1 = new SuffixTreeNode(input.substring(i + 1),newNode);
							n1.addOwner(input);
							newNode.addChildNode(n1);
						}
						SuffixTreeNode n2 = new SuffixTreeNode(node.getValue().substring(i + 1),newNode);
						newNode.addChildNode(n2);
						n2.addOwner(input);
					}
				}
			}
		}
		if(!hasPut){
			SuffixTreeNode newNode = new SuffixTreeNode(input,inputNode);
			inputNode.addChildNode(newNode);
			newNode.addOwner(input);
		}
	}
	
	public int getLevel(SuffixTreeNode node){
		int i = 1;
		if(node == root){
			return 0;
		}
		while(node.getParent() != root){
			i++;
			node = node.getParent();
		}
		return i;
	}
	
	public void printTree(){
		doPrint(root);
	}
	
	private void doPrint(SuffixTreeNode node){
		System.out.println(node.getValue() + " " + getLevel(node) + " "+node.getOwners().size());
		for(SuffixTreeNode child:node.getChildNodes()){
			doPrint(child);
		}
	}
	
	public SuffixTreeNode collectDeepestNodeWithMultipleOwners(){
		List<SuffixTreeNode> list = doCollectNodeWithMultipleOwners(root);
		int max = 1;
		SuffixTreeNode result = new SuffixTreeNode("",null);
		for(SuffixTreeNode node:list){
			int level = getLevel(node);
			if(level >= max){
				if(level == max){
					if(node.getValue().length() > result.getValue().length()){
						max = level; 
						result = node;
					}
				}else{
					max = level;
					result = node;
				}
			}
		}
		return result;
	}
	
	public List<SuffixTreeNode> doCollectNodeWithMultipleOwners(SuffixTreeNode node){
		List<SuffixTreeNode> nodes = new ArrayList<SuffixTreeNode>();
		if(node.getOwners().size() >= 2){
			nodes.add(node);
		}
		for(SuffixTreeNode child:node.getChildNodes()){
			nodes.addAll(doCollectNodeWithMultipleOwners(child));
		}
		return nodes;
	}
}
